package com.imooc.distributedemo.rithm;

/**
 * 快速排序
 */
public class QuikSortSolution {

    public static void quikSort(int[] arr,int begin,int end){
        if(end<=begin){
            return;
        }
        int pivot = partition(arr,begin,end);
        quikSort(arr,begin,pivot-1);
        quikSort(arr,pivot+1,end);
    }

    private static int partition(int[] a, int begin, int end) {
        // pivot标杆元素  counter 小于pivot元素的个数
        int pivot = end;
        int counter = begin;
        for (int i = 0; i < end; i++) {
            if(a[i]<a[pivot]){
                int temp = a[counter];
                a[counter] = a[i];
                a[i] = temp;
                counter++;
            }
        }
        int temp = a[pivot];
        a[pivot] = a[counter];
        a[counter] = temp;
        return counter;
    }

    public static void main(String[] args) {
        int[] arr= {3,6,11,7,2,9,123,77,34};
        quikSort(arr,0,arr.length-1);
        System.out.println(arr);
    }
}
